package algorithm.leetcode.I201to400;

import algorithm.leetcode.TreeNode;

/**
 * 如果两个节点值都小于根节点，说明他们都在根节点的左子树上，我们往左子树上找
 * 如果两个节点值都大于根节点，说明他们都在根节点的右子树上，我们往右子树上找
 * 如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。
 *
 * 作者：sdwwld
 * 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-3c/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */

public class Q235 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val >= Math.min(p.val, q.val) && root.val <= Math.max(p.val, q.val)) return root;
        else if (root.val < Math.min(p.val, q.val)) return lowestCommonAncestor(root.right, p, q);
        else return lowestCommonAncestor(root.left, p, q);
    }
}
